

/**
 * 向最小堆里添加一个节点
 * @date 2023-04-05
 * @param {any} heap  最小堆
 * @param {any} node 节点
 * @returns {any}
 */
function push(heap, node) {
    // 获取元素的数量
    const index = heap.length;
    // 先把获取到的元素放在数组的尾部
    heap.push(node);
    // 向上调整到合适的位置
    siftUp(heap, node, index);
}


/**
 * 查看最小堆顶的元素
 * @date 2023-04-05
 * @param {any} heap
 * @returns {any}
 */
function peek(heap) {
    const first = heap[0];
    return first === undefined ? null : first;
}

/**
 * 弹出最小堆顶元素
 * @date 2023-04-05
 * @param {any} heap
 * @returns {any}
 */
function pop(heap) {
    // 去除数组中的第一个（堆顶元素）
    const first = heap[0];
    if (first !== undefined) {
        // 弹出数组中的最后一个元素
        const last = heap.pop();
        if (last !== first) {
            heap[0] = last;
            siftDown(heap, last, 0);
        }
    }
}

/**
 * 向上调整某个节点，使其位于正确的位置
 * @date 2023-04-05
 * @param {any} heap 最小堆
 * @param {any} node 节点
 * @param {any} i 节点所在的索引
 * @returns {any}
 */
function siftUp(heap, node, i) {
    let index = i;
    while (true) {
        // 获取父节点的索引
        const parentIndex = index - 1 >>> 1;
        // 获取父节点
        const parent = node[parentIndex];
        // 如果父节点存在且父节点比子节点要大
        if (parent !== undefined && compare(parent, node) > 0) {
            // 把儿子的值给父索引
            heap[parentIndex] = node;
            // 把父亲的值给子索引
            heap[index] = parent;
            // 让index等于父亲的索引
            index = parentIndex;
        } else {
            // 如果子节点比父节点要大就退出
            return;
        }
    }
}

/**
 * 向下调整某个节点，使其位于正确的位置
 * @date 2023-04-05
 * @param {any} heap 最小堆
 * @param {any} node 节点
 * @param {any} i 节点所在的索引
 * @returns {any}
 */
function siftDown(heap, node, i) {
    let index = i;
    const length = heap.length;
    while (index < length) {
        // 左子节点的索引
        const leftIndex = (index + 1) * 2 - 1;
        const left = heap[leftIndex];
        // 右子节点的索引
        const rightIndex = leftIndex + 1;
        const right = heap[rightIndex];
        // 如果左子节点存在且左子节点比父节点要小
        if (left !== undefined && compare(left, node) < 0) {
            // 如果右节点存在且右节点比左节点要小，则父节点与右子节点交换位置
            if (right !== undefined && compare(right, left) < 0) {
                heap[index] = right;
                heap[rightIndex] = node;
                index = rightIndex;
            } else {
                // 否则就跟左子节点交换
                heap[index] = left;
                heap[leftIndex] = node;
                index = leftIndex;
            }
        } else if (right !== undefined && compare(right, node) < 0) {
            heap[index] = right;
            heap[rightIndex] = node;
            index = rightIndex;
        } else {
            return;
        }
    }
}

function compare(a, b) {
    const diff = a.sortIndex - b.sortIndex;
    return diff !== 0 ? diff : (a.id - b.id);
}

let heap = [];
let id = 1;
push(heap, { sortIndex: 1, id: id++ });
push(heap, { sortIndex: 2, id: id++ });
push(heap, { sortIndex: 3, id: id++ });
push(heap, { sortIndex: 4, id: id++ });
push(heap, { sortIndex: 5, id: id++ });
push(heap, { sortIndex: 6, id: id++ });
push(heap, { sortIndex: 7, id: id++ });
pop(heap)
console.log(peek(heap), heap);